#include "hash.h"

#include "lista.h"
#include "string.h"
#include <stdlib.h>
#include <stdbool.h>

#define BLOQUEINICIAL 257
#define FCMAX 0.8
#define FCMIN 0.2
#define MASTAM 2
#define MENOSTAM 0.5

struct hash {
	size_t cantidad;
	size_t tamanio;
	lista_t **tabla;
	hash_destruir_dato_t destruir_dato;
};

struct hash_iter {
	lista_t **lista;
	lista_iter_t *iterador;
	size_t cantidad;
	size_t visitados;
};

typedef struct hash_nodo {
	char *clave;
	void *valor;
} hash_nodo_t;						


void hash_nodo_destruir(void *dato_nodo);
hash_nodo_t *hash_nodo_crear(const char *clave, void *valor);
size_t funcion_hash(const char *clave, size_t n);

bool hash_redimencionar (hash_t* hash, size_t nuevo_tam)
{
	lista_t** nueva_tabla = calloc (nuevo_tam, sizeof (lista_t*));
	hash_iter_t* iter = hash_iter_crear (hash);
	const char* clave;
	void* dato;
	hash_nodo_t* nodo;
	size_t pos;

	while (! hash_iter_al_final (iter))
	{
		clave = hash_iter_ver_actual (iter);
		dato = hash_obtener (hash, clave);
		nodo = hash_nodo_crear (clave, dato);
		pos = funcion_hash (clave, nuevo_tam);

		if (!nueva_tabla[pos])
			nueva_tabla[pos] = lista_crear ();
		
		lista_insertar_ultimo (nueva_tabla[pos], nodo);
		hash_iter_avanzar (iter);
	}

	hash_iter_destruir (iter);

	for (int i = 0; i < hash->tamanio; ++i)
		if (hash->tabla[i])
			lista_destruir (hash->tabla[i], hash_nodo_destruir);

	free (hash->tabla);
	hash->tabla = nueva_tabla;
	hash->tamanio = nuevo_tam;
	return true;
}

hash_nodo_t *hash_nodo_crear(const char *clave, void *valor)
{
	hash_nodo_t *nodo = (hash_nodo_t *)malloc(sizeof(hash_nodo_t));

	if (!nodo)
		return NULL;
	
	nodo->clave = malloc(sizeof(char)*(strlen(clave)+1));
	
	if (!nodo->clave)
		{
			free(nodo);
			return NULL;
		}
	
	strcpy(nodo->clave,clave);
	nodo->valor = valor;

	return nodo;
}

void hash_nodo_destruir(void *nodo_dato)
{
	if (!nodo_dato)
		return;

	hash_nodo_t* nodo = nodo_dato;

	free(nodo->clave);
	free(nodo);
}

hash_t *hash_crear(hash_destruir_dato_t destruir_dato)
{
	hash_t *hash = malloc(sizeof(hash_t));

	if (!hash)
		return NULL;
	
	hash->tabla = calloc(BLOQUEINICIAL, sizeof(lista_t *));
	
	if (!hash->tabla)
		{
			free(hash);
			return NULL;
		}
	
	hash->tamanio = BLOQUEINICIAL;
	hash->destruir_dato = destruir_dato;
	hash->cantidad = 0;
	return hash;
}

size_t funcion_hash(const char *clave, size_t n)
{
	size_t valor = 0;
 	while(*clave != '\0')
	{
   		valor *= 31;
  		valor += *clave;
               	clave++;
       	}
 	
	return valor % n;
}

/* Funcion interna. Recibe una lista y busca el nodo con la clave asociada y
	devuelve un iterador sobre la lista. Si no lo encuentra, devuelve NULL.
*/
lista_iter_t *nodo_buscar(const lista_t *lista, const char *clave)
{
	if (!lista)
		return NULL;

	if (!clave)
		return NULL;
	
	if (lista_esta_vacia(lista))
		return NULL;
	
	lista_iter_t *iter = lista_iter_crear(lista);
	
	if (!iter)
		return NULL;

	while (!lista_iter_al_final(iter))
		{
			hash_nodo_t *nodo = lista_iter_ver_actual(iter);
			
			// En caso de que pase algo desagradable.
			if (!nodo)
				{
					lista_iter_destruir(iter);
					return NULL;
				}

			// Encontrado.
			if (!strcmp(clave,nodo->clave))
				return iter;
			
			lista_iter_avanzar(iter);
		}

	// No encontrado.
	lista_iter_destruir(iter);
	return NULL;
}

bool hash_guardar(hash_t *hash, const char *clave, void *dato)
{
	if (!hash)
		return false;

	if (!clave)
		return false;

	if (hash->cantidad/hash->tamanio >= FCMAX)
		if (!hash_redimencionar (hash, MASTAM * hash->tamanio))
			return false; 

	size_t pos = funcion_hash(clave,hash->tamanio);

	lista_t *lista = hash->tabla[pos];

	lista_iter_t *iter = nodo_buscar(lista,clave);

	hash_nodo_t *nodo;

	// Clave encontrada, reemplazamos el contenido.
	if (iter)
		{
			nodo = lista_iter_ver_actual(iter);		

			lista_iter_destruir(iter);			

			if (hash->destruir_dato)
				hash->destruir_dato(nodo->valor);

			nodo->valor = dato;

			return true;
		}

	if (!lista)
		{
			lista = lista_crear();

			if (!lista)
				return false;

			hash->tabla[pos] = lista;
		}

	nodo = hash_nodo_crear(clave,dato);

	if (!nodo)
		{
			/* Si la lista fue creada y está vacía
				la liquidamos para hacer memoria.
			*/
			if (lista_esta_vacia(lista))
				{
					lista_destruir(lista,NULL);
					hash->tabla[pos] = NULL;
				}
				
			return false;
		}

	// Si falla destruímos el nodo.
	if (!lista_insertar_primero(lista,nodo))
		{
			hash_nodo_destruir(nodo);

			if (lista_esta_vacia(lista))
				{
					lista_destruir(lista,NULL);
					hash->tabla[pos] = NULL;
				}

			return false;
		}

	hash->cantidad++;
	return true;
}

void *hash_borrar(hash_t *hash, const char *clave)
{
	if (!hash)
		return NULL;

	if (!clave)
		return NULL;

	if (hash->cantidad/hash->tamanio <= FCMIN)
		if (!hash_redimencionar (hash, hash->tamanio * MENOSTAM))
			return false; 

	size_t pos = funcion_hash(clave,hash->tamanio);

	lista_t *lista = hash->tabla[pos];
	
	lista_iter_t *iter = nodo_buscar(lista,clave);

	if (!iter)
		return NULL;

	hash_nodo_t *nodo = lista_borrar(lista,iter);

	if (lista_esta_vacia(lista))
		{
			lista_destruir(lista,NULL);
			hash->tabla[pos] = NULL;
		}

	lista_iter_destruir(iter);

	if (!nodo)
		return NULL;
	
	void *dato = nodo->valor;

	hash_nodo_destruir(nodo);

	hash->cantidad--;
	return dato;
}

void *hash_obtener(const hash_t *hash, const char *clave)
{
	if (!hash)
		return NULL;

	if (!clave)
		return NULL;

	size_t pos = funcion_hash(clave,hash->tamanio);
	
	lista_t *lista = hash->tabla[pos];
	
	if (!lista)
		return NULL;

	// Hay lista, debemos iterar en ella.
	lista_iter_t *iter = nodo_buscar(lista,clave);
	
	if (!iter)
		return NULL;

	hash_nodo_t *nodo = lista_iter_ver_actual(iter);

	lista_iter_destruir(iter);

	if (!nodo)
		return NULL;
	
	return nodo->valor;
}

bool hash_pertenece(const hash_t *hash, const char *clave)
{
	if (!hash)
		return false;

	if (!clave)
		return false;

	size_t pos = funcion_hash(clave, hash->tamanio);

	lista_t *lista = hash->tabla[pos];

	if (!lista)
		return false;

	lista_iter_t *iter = nodo_buscar(lista,clave);

	if (!iter)
		return false;

	lista_iter_destruir(iter);

	return true;
}

size_t hash_cantidad(const hash_t *hash)
{
	if (!hash)
		return 0;

	return hash->cantidad;
}

void hash_destruir(hash_t *hash)
{
	if (!hash)
		return;

	for (size_t i = 0; i < hash->tamanio; i++)
		{
			lista_t *lista = hash->tabla[i];

			if (lista)
				{
					while (!lista_esta_vacia(lista))
						{
							hash_nodo_t *nodo = lista_borrar_primero(lista);
							if (hash->destruir_dato)
								hash->destruir_dato(nodo->valor);
							hash_nodo_destruir(nodo);
						}
					lista_destruir(lista,NULL);
				}
		}

	free(hash->tabla);
	free(hash);
}

hash_iter_t *hash_iter_crear(const hash_t *hash)
{
	hash_iter_t *iter = malloc(sizeof(hash_iter_t));

	if (!iter)
		return NULL;

	iter->lista = hash->tabla;

	if (hash->cantidad)
	{
		while (!*iter->lista)
			(iter->lista)++;

		iter->iterador = lista_iter_crear (*iter->lista);
		if (!iter->iterador)
		{
			free (iter);
			return NULL;
		}
	}
	else
		iter->iterador = NULL;

	iter->visitados = 0;
	iter->cantidad = hash->cantidad;

	return iter;
}

bool hash_iter_avanzar(hash_iter_t *iter)
{
	if (!iter)
		return false;

	if (hash_iter_al_final (iter))
		return false;

	lista_iter_avanzar (iter->iterador);
	
	if (lista_iter_al_final (iter->iterador) && !(iter->visitados+1 == iter->cantidad))
	{	
		lista_iter_destruir (iter->iterador);
		(iter->lista)++;
		
		while (!(*iter->lista))
		{
			while (!(*iter->lista))
				(iter->lista)++;
			//si hay listas vacias las elimina
			if (lista_esta_vacia (*iter->lista))
			{
				lista_destruir (*iter->lista, NULL);
				*iter->lista = NULL;
			}
		}

		iter->iterador = lista_iter_crear (*iter->lista);

		if (!iter->iterador)
			return false;

	}

	
	iter->visitados ++;
	return true;
}

const char *hash_iter_ver_actual(const hash_iter_t *iter)
{
	if (!iter)
		return NULL;

	if (!iter->iterador)
		return NULL;

	if (hash_iter_al_final (iter))
		return NULL;

	hash_nodo_t* nodo = lista_iter_ver_actual (iter->iterador);

	if (!nodo)
		return NULL;

	return nodo->clave;
}

bool hash_iter_al_final(const hash_iter_t *iter)
{
	if (!iter || !iter->iterador)
		return true;

	return iter->visitados == iter->cantidad;
}

void hash_iter_destruir(hash_iter_t* iter)
{
	if (!iter)
		return;

	lista_iter_destruir (iter->iterador);
	free(iter);
}

